Non-volatile semiconductor memories employing a NAND flash memory chip (hereinafter, referred to as “flash memories”) are known. With a flash memory, data is written and read in units called physical pages while data is erased in units called blocks which are constituted by a plurality of physical pages.
In a flash memory, due to the properties thereof, it is impossible to directly rewrite data that has already been written onto a physical page. Thus, rewriting of data of a flash memory is performed by writing data in a free physical page. With this method, the number of free physical pages in the flash memory decreases every time rewriting is performed. Therefore, unnecessary data in the flash memory must be erased in block units so as to restore free physical pages. This process is referred to as reclamation. Reclamation is performed according to the following procedure. (1) Data of a valid physical page in a block is duplicated to a physical page of another block. (2) Data of all physical pages in the block is erased.
As described above, with a flash memory, data of a certain physical page is migrated to another physical page. For this purpose, a flash memory includes a logical-physical translation table for translating an address of a logical page (a logical address) to an address of a physical page (a physical address). When a flash memory receives a write request regarding a logical address, the flash memory uses the logical-physical translation table to translate the logical address to a physical address and writes data to a physical page associated with the physical address. In addition, when a flash memory executes reclamation and migrates data of a certain physical page to another physical page, the flash memory changes the correspondence between a logical page and a certain physical page (a migration source) in the logical-physical translation table to a correspondence between the logical page and another physical page (a migration destination). In this manner by using a logical-physical translation table, a flash memory hides migration of data between physical pages inside the flash memory, from the outside.
A data size of a logical-physical translation table tends to increase as a capacity of a flash memory increases. PTL 1 describes increasing a logical capacity of a flash memory by compressing user data to be stored in the flash memory. When a logical capacity is increased in this manner, the data size of a logical-physical translation table further increases. Therefore, a logical-physical translation table with a large data size ends up oppressing the capacity of a main memory (for example, a DRAM). In regards to this issue, NPL 1 describes evacuating a part of a logical-physical translation table from a main memory to a flash memory and reading (staging) the evacuated part to the main memory when necessary. Accordingly, the logical-physical translation table with a large data size can be prevented from oppressing the capacity of the main memory.